package com.tys.algorithm.advanced.test.class27;

public class Code01_KMP {

    //
    public static int getIndexOf(String s1, String s2) {
        //无效条件返回-1
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        //转字符数组
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        //没有开头，只有比对位置
        int x = 0; //str1比对位置
        int y = 0; //str2比对位置
        // 求next数组：O(M) m <= n
        int[] next = getNextArray(str2);
        // O(N)
        while (x < str1.length && y < str2.length) {

            if (str1[x] == str2[y]) {
                //相等匹配了：str1和str2向右下一个位置
                x++;
                y++;
            } else if (next[y] == -1) {
                // 只有0位置是-1：y == 0，
                // 不能向左了，下一个
                x++;
            } else {
                //Y根据next中的值向左跳，等同于向右推
                y = next[y];
            }
        }
        // y 越界了则: s1中匹配了所有s2，返回s1中的匹配开始位置=x-y，
        // y 不越界：s1中没有匹配的s2，返回 -1
        return y == str2.length ? x - y : -1;
    }

    //求next数组
    public static int[] getNextArray(char[] str2) {
        //0位置是-1
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        //0位置-1
        next[0] = -1;
        //1位置0
        next[1] = 0;
        //从2位置开始求
        int i = 2; // 目前在哪个位置上求next数组的值
        //cn一直和i-1位置比
        //因为i初始=2：cn初始是0位置和1位置比
        int cn = 0; // 当前是哪个位置的值再和i-1位置的字符比较
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) { // 配成功的时候
                //i=cn+1
                //++cn 让 i+1使用i位置的正确值cn+1
                next[i++] = ++cn;
            } else if (cn > 0) {
                //cn向左
                cn = next[cn];
            } else {
                //向左不了，则为0
                next[i++] = 0;
            }
        }
        return next;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (getIndexOf(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

}
